home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ASME's Mechanical Engine…ing Toolkit 1997 December
/
ASME's Mechanical Engineering Toolkit 1997 December.iso
/
ai
/
prlg195b.lzh
/
PUZZLES.LZH
/
RIVER.PRO
< prev
next >
Wrap
Text File
|
1986-07-20
|
6KB
|
131 lines
/* Farmer-goat-wolf-cabbage problem
The Prolog code below solves the farmer-goat-wolf-cabbage
problem.
The problem details are as follows:
1. A farmer is on one side of a river with a goat,
wolf, and cabbage. A boat is at his disposal
to get himself and his companions/baggage
to the other side.
2. Only the farmer can row the boat, either alone
or with one passenger.
3. The following pairs cannot co-exist without the
stabilizing presence of the farmer:
a. wolf and goat - wolf will eat the goat
b. goat and cabbage - goat will eat the cabbage
The following predicates have been coded to solve the problem.
predicate description
********* *********************************
solvex the 'main' predicate, highest level
problem solving call
move generates a move for the game
member tests a state to see if it has been used
before, i.e., prevents a logical loop.
badx lists the bad, or disallowed, states.
prt prints the problem solution, or the states
traversed.
The following statement initiates the problem solving process:
solvex(statex(south,south,south,south),[],[]).
This statement says that the farmer, goat, wolf, and cabbage
(respectively) are on the south side of the river (the starting
state for the game) and that the solution and print lists are
initially empty.
.PA
The solvex rules are given below. The rule immediately below must
come first. */
solvex(statex(north,north,north,north),Solution_list,Print_list) :-
prt(Print_list),!.
/* This statement (above) terminates the program when everybody
is on the north side of the river and generates a listing of the
solution.
The statement below adds the initial state on the solution and
print lists, generates the first move, tests the move for correctness,
stores that move on the solution and print lists, and calls
solvex to generate the next move in the game. */
solvex(statex(south,south,south,south),[],[]) :-
move(Mtype,statex(south,south,south,south),
statex(Mf1,Mw1,Mg1,Mc1)),
not(badx(statex(Mf1,Mw1,Mg1,Mc1))),
solvex(statex(Mf1,Mw1,Mg1,Mc1),
[[Mf1,Mw1,Mg1,Mc1],
[south,south,south,south]],
[[Mtype,Mf1,Mw1,Mg1,Mc1],
[start,south,south,south,south]]).
/* The next statement/predicate does most of the work. It takes the
input state, generates another state, i.e., a move in the game,
checks to see if it is a legal move, checks to see if that state
has been used before (to prevent a loop, or circular reasoning),
saves the state on both the solution and print lists, and
calls itself recursively to generate yet another move. */
solvex(statex(Mfarmer,Mwolf,Mgoat,Mcabbage),Solution_list,Print_list) :-
move(Mtype,statex(Mfarmer,Mwolf,Mgoat,Mcabbage),
statex(Mf1,Mw1,Mg1,Mc1)),
not(badx(statex(Mf1,Mw1,Mg1,Mc1))),
not(member([Mf1,Mw1,Mg1,Mc1],Solution_list)),
solvex(statex(Mf1,Mw1,Mg1,Mc1),
[[Mf1,Mw1,Mg1,Mc1]|Solution_list],
[[Mtype,Mf1,Mw1,Mg1,Mc1]|Print_list]).
/* The bad, or disallowed states are listed below */
badx(statex(north,south,south,_)). /* wolf and goat on south side*/
badx(statex(south,north,north,_)). /* wolf and goat on north side*/
badx(statex(north,_,south,south)). /* goat and cabbage on south */
badx(statex(south,_,north,north)). /* goat and cabbage on north */
/*
.PA
The legal moves are described below. The fact that we have
described the disallowed states above allows the use of variables
in the description below rather than spelling out all of the legal
moves in excrutiating detail.
These moves have been ordered to produce one solution as fast as
possible. The eventual success of the program does not depend on
the ordering although different solutions may result with other
orderings. */
move(goat,statex(south,Mz,south,Ma),statex(north,Mz,north,Ma)).
move(farmer,statex(south,Mx,Ma,Mb),statex(north,Mx,Ma,Mb)).
move(wolf,statex(south,south,Mz,Ma),statex(north,north,Mz,Ma)).
move(goat,statex(north,Mz,north,Ma),statex(south,Mz,south,Ma)).
move(cabbage,statex(south,Mz,Ma,south),statex(north,Mz,Ma,north)).
move(farmer,statex(north,Mz,Ma,Mb),statex(south,Mz,Ma,Mb)).
move(wolf,statex(north,north,Mz,Ma),statex(south,south,Mz,Ma)).
move(cabbage,statex(north,Mz,Ma,north),statex(south,Mz,Ma,south)).
/* The member predicate definition */
member(X,[X|_]).
member(X,[_|L]) :- member(X,L).
/* Predicate to print the final result */
prt([]) :- nl.
prt([X|L]) :- write(X),nl,prt(L).
/* That's all folks */